Many large corporations rely on a wide variety of different and often disparate computer systems that were implemented at various times and circumstances. The multiplicity of systems adds dramatically to a company's costs. Multiplicity also reduces efficiency and a company's operational economies of scale. Also, employees require extensive training in order to be able to use each of the different systems. The cost and inconvenience of upgrading all of these components into one easy to use computer system is also enormous.
Even if a company does manage to upgrade and merge all of its operations into a single computer system, when it wants to collaborate, merge, participate in joint ventures, at least some of the above-noted problems will arise. But, many companies do not upgrade applications because of the expense involved. Thus, there are many systems still in operation that require integration, but are very difficult to integrate, such as, systems that are only terminal-accessible.
Terminal-accessible systems, such as, one that requires access via a 3270 terminal, were the predominant applications architecture prior to the proliferation of personal computers (“PC”). Unlike PCs, such terminals were not capable of running software independently of a mainframe. While use of PCs has become widespread, there are still terminals in operation, as well as many terminal-accessible systems. In many places, PCs running software called 3270 emulation connect remotely to a computer running 3270 applications. This allows a PC to connect to a terminal-accessible system through an interface that functions like a terminal.
SQL (Structured Query Language) is a standard programming language adopted by the American National Standards Institute and the International Organization for Standardization for getting information from and updating a database. Many databases, such as, Access databases, support SQL queries.
As a result of the continued use of old systems, companies have begun integrating and automating computer systems. Integration, however is not an easy task to accomplish. To integrate many different systems into one user-friendly graphical user interface (“GUI”), a program must in some way control another program or access its data directly. So, for example, while arranging a purchase, a salesman may need to: (1) access a Legacy database to verify that a product is in stock and update inventory, (2) access a separate database to update the customer's information and (3) access a separate a website and affiliated database to arrange for shipping. Accessing each of these systems is both time consuming and redundant. The salesman would have to enter the product and customer information three different times each time he/she placed an order. In addition, the salesman would have to be familiar with how to navigate each of these systems.
By integrating all of these systems into one GUI, the salesman would only have to learn one system. Moreover, that employee could be trained quicker, and would not have to re-enter the same information more than once. The difficulty would arise in designing a GUI that can navigate all three of the above-exemplified systems. As previously noted, an interface would have to be designed for each system. While one standard interface could be used for the shipping website, such as a FedEx or UPS website, each Legacy and Access database is designed specifically for the company using it. Each company has unique information that it stores in its databases about products and customers. Accordingly, for each company the arduous task of designing software to interface with its various databases must be undertaken.
There are three distinct techniques for one computer application to talk to another computer application--through the data layer, business logic layer or presentation layer. System A's business logic layer 52 must communicate with system B's data layer 58, business logic layer 57 or presentation layer 56 to access system B 55. Access through the data layer 58 allows direct modification of the data in system B's 55 database. Unfortunately, it is extremely time consuming, expensive and error-prone to interface directly with a system's data layer. As a result, many systems do not allow any direct manipulation or access to the data.
The second method for one system to communicate with a second system is though the second system's business logic layer. For system A 50 to access system B 55 through system B's business logic layer, a transaction interface needs to be developed for system B 55. As is the problem with accessing another system through the data layer, developing a transaction interface to access a system though its business logic layer is time consuming and expensive.
The third method for one system to communicate with a second system is through the second system's presentation layer. While not nearly as expensive as creating a transaction interface to access the business logic layer or accessing the data directly, interfacing with the presentation layer has problems. A particular problem is that the integrating application must wait an appropriate length of time after entering commands to insure that the program has moved to a new state after the commands were entered. However, the time that a state change takes is erratic, so this is problematic.
Another problem is the unpredictable nature of applications in general. When an application does not go to the expected state after a command is entered, a scripted agent is unable to recover without specific instructions being written to cover that situation. This is difficult because there is a near infinite number of ways that an application can behave.
One solution to the state change problem is to program the integrating application to determine which screen it is on. If the application being controlled used screens with unique identifiers, then screen identification information is accessible. If a screen has a unique identifier, the integrating application merely has to look at the unique identifier to know what screen it is on. Only about 20% or less of Legacy systems have applications that use screens with unique identifiers, so it is not an overall solution.
Another solution to the screen recognition issue is for the programmer to select regions of the screen for the software to examine in order to determine which screen is active. However, when a host system or application has numerous different screens it can be a time consuming and error-prone task for a programmer to determine which regions will work efficiently or work at all.
A programmer also has to determine how each screen is reached and from which screens it can be reached. This requires mapping the host application. To map the host application, a list of screens is created in the order they appear during navigation. Each entry in the list includes screen identification information. Necessary information (by using, for example, key words) include: (i) the action that takes place on that screen, (ii) attention identifier keys used on that screen, (iii) the next screen to be displayed, and (iv) the time it takes to navigate from one screen to the next screen.
The next step is to create an itemized description for each screen. This description includes the type of field (read-only, button, etc.), the possible values this field could hold and the appropriate response for each possible value, whether the field can be written to, what can be written to it, the location on the screen of the field, and the length of the field for each field in each screen.
Once this information is compiled, a directed graph or state diagram is created to illustrate the operation of the system. From the directed graph or state diagram, the code to interface with a system can be written. This must be repeated for each system that is to be integrated.
As can be seen from above, even under the best circumstances, the task of integrating disparate databases and computer software is complex, time consuming and expensive. Therefore, there exists a need in the art for software to simplify the process of modeling various systems and seamlessly integrating information access over extended networks.
Artificial Intelligence (AI) Planning and Scheduling is a subject area within the field of Artificial Intelligence that deals with the problem of reasoning about activities and then sequencing them. Action sequences constitute plans that, if executed, represent a means of achieving a specific goal. Planning algorithms do not address the problem of performing these actions; the integration of planning and acting is the focus of “Intelligent Agent” research. The focus of planning research is on the representation of actions, storage and retrieval of actions, time conflict, resources, priorities, action reasoning, time and space complexity, proving correctness, proving solvability (within a reasonable amount of time), knowledge representation, problem complexity and scale, empirical studies demonstrating run-time behavior, real-world applications, uncertainty, model coverage and plan domain learning. Scheduling is a sub-field of planning that deals specifically with planning resource allocations over time to achieve specific goals within minimal time frames and with minimal resource allocation. A brief overview of AI Planning and Scheduling (hereinafter simply referred to as “Planning”) is discussed below, including a short history, a description of plan representation, planning algorithms and a look at the future of planning.
Planning has not become a mainstream development technique for a variety of reasons. Until recently, planning was CPU and space inefficient. Planning uses a declarative representation of program behavior, which is not taught in standard programming classes. There are no commercially successful planning tools, and, in the past, planners had a very narrow range of application. Recent developments in planning algorithms and in CPU and space availability have prompted interest in planning architectures. Planners have successfully been applied to a wide range of problems. Further, recent developments, such as planning based method of handling Presentation Layer Automation, represents a shift towards commercial acceptance of planning and paves the way for use within mainstream software development.
There are two distinct types of planning systems: Propositional and Decision Theoretic. Propositional planning deals with the world in terms of actions that are composed of propositional statements about action pre-condition and effects. Decision Theory combines Probability Theory with Utility Theory, and treats the world as a set of states over which an action policy determines likely transitions between states. Decision Theoretic planning involves the calculations of probabilities, and does not provide mechanisms for demand-time goal directed behavior. Rather, Decision Theoretic systems attempt to pre-compute the likelihood that some action in response to some observation will lead to a situation that will ultimately allow a goal to be achieved. Consider the decision to buy a car. There are many tests that could be performed and many issues that need to be considered. Ultimately the decision to move forward should be based on a rational assessment of a reasonable set of tests. While Propositional Planning determines a path to a goal by chaining together logical propositions about how the world behaves, Decision Theoretic planning determines a path to a goal by calculating probabilities of expected outcomes and choosing the most likely course of action. There have been some attempts to merge these two fields, but generally they represent two completely distinct areas.
AI planning is closely related to state-space search, problem reduction and means-end analysis used in problem solving, and to other areas of AI such as theorem proving and situation calculus. The first major planning system was called STRIPS (Stanford Research Institute “SRI” Planning and Scheduling), and was the planning component of the Shakey robot project at SRI. A series of planners have emerged since then, solving many of the major problems of AI planning. One of the early problems discovered in planners was that of interleaving. Non-interleaved plans cannot find goals where sub-goals must be protected halfway through a plan.
Task networks allowed plans to be partially ordered, i.e. not all sequences of actions need to be ordered in a valid plan. More recently, several advances in AI planning have made planners more commercially viable. Early planners suffered from memory use and run-time problems. Newer algorithms guarantee a solution (if one exists) within polynomial time and space (defined below in the Glossary). A disjunctive planner retains the current plan-set without splitting its components into different search branches. Other known planner employed this idea to generate constraints, which are solved using a constraint solver. More recently, TLPlan is the one of the most successful planners in terms of memory efficiency and speed, and is leading the way with a slightly different approach to planning. TLPlan employs heuristic search, which has been found to work well in the area of problem solving. Other planners also use heuristic search. Heuristic search techniques have been shown to be quite fast, and are the basis for many interesting problem solvers such as game systems (some of the groundbreaking discoveries in heuristic search were made at the University of Alberta by Tony Marsland and Jonathan Schaefer). At one time, it was thought that heuristic search could not be applied to planning due the branching factor in planning problems, and the large amount of backtracking that would be required. Recent advances, however, in both heuristic search and in planning have lead to breakthroughs, which are revolutionizing planning systems.
Graphplan is one algorithm that has been very successful in the planning community. When Graphplan arrived in 1995, it generated a lot of interest because of its ability to solve plans for any order of magnitude that was faster than previous algorithms. Since Graphplan was introduced, several other algorithms have been developed that are equally competitive. The basic idea behind Graphplan planning is simple and easily understood in terms of requirements and deliverables. A plan can be thought of as a sequence of activities, where early activities are performed, generating results that, in turn, feed into later activities as deliverables. The overall planning process is prompted by the desire of some agent to achieve some goal. Along with a goal and a knowledge base representing all the actions that can be performed, the planning process requires knowledge about the state of the world at the time of planning, i.e. the initial state.
Consider a plan for going out to the movies. The first activity is to choose a movie, the next is to drive to the theatre complex, then purchase a ticket, optionally purchase some snacks, go into the theatre, and finally watch the movie. Doing these activities out of sequence does not make any sense. The results of each step in the process, and their requirements, impose a logical ordering of the activities. Choosing a movie is important as a first step because the result is a requirement for driving. Driving is important because the result is arriving at some desired location. Purchasing a ticket is a pre-requisite for getting into the theatre. Going into the theatre is a pre-requisite for actually viewing the movie. A planner is able to take all of the possible actions that apply to the problem, and is able to arrange them according to how the preconditions (requirements) mesh with the effects (deliverables) of each action. Although the task seems simple, there are many nuances to the problem that make planning an interesting research topic).
The term classical planning is often used to describe simple worlds with initial states, goal states and a set of deterministic actions. Although the general planning problem is much more complicated, classical planning is an important conceptual step to understanding general planning. Consider the problem of transporting two packets from earth to the moon using a single rocket. This Rocket problem is an example of a propositional planning problem. The problem comprises three classic planning operations: Load, Unload, and Fly. There are two objects, A and B, and three locations, Earth, Moon and Rocket. The Load operation applied to a particular container has a pre-condition that the container is not loaded. The effect of the Load operation is that the container becomes “Loaded.” The following notations are used in the discussion of this problem:                “A” refers to Package A and Load A means Load Package A.        “B” refers to Package B and Load B means Load Package B.        “R” refers to the rocket.        State (Proposition): Full description of the entities and the properties of the world at a particular time        Action: Progressive alteration of states that result in an observable effect on the external world        Initial Conditions: Initial state of the world        Goals: Desired property of the world state        Plan: Detailed and systematic formulation of actions        
In planning language of PDDL, the rocket problem would be defined in the following way:
(define (domain rocket)  (:predicates (at ?r - rocket ?from - place)    (in ?c- cargo ?r - rocket))(:action move  :parameters ( ?r - rocket ?from ?to - place)  :precondition (and (at ?r ?from))  :effect (and (at ?r ?to) (not (at ?r ?from)))(:action unload  :parameters (?r - rocket ?p - place ?c - cargo)  :precondition (and (at ?r ?p) (in ?c ?r))  :effect (and (not (in ?c ?r) (at ?c ?p)))(:action load  :parameters (?r - rocket ?p - place ?c - cargo)  :precondition (and (at ?r ?p) (at ?c ?p) )  :effect (and (not (at ?c ?p)) (in ?c ?r) ))
The following syntax is used to make a request of the planner to find a plan:
(define (problem rocketProblem)  (:domain rocket)  (:objects A B - cargo    E M - places    R - rocket)  (:init (at A E) (at B E) (at R E))  (:goal (and (at A M) (at B M) )
The Graphplan algorithm requires the following:                A STRIPS-like domain (a set of operators such as Load, Unload, Move)                    Each operator has a set of pre-conditions                            A rule that must be true prior to the use of the operator                                    Each operator has a set of effects                            A rule that must be true after the use of the operator                                                A set of objects (such as Rocket or Package A)        A set of predicates that can be assessed regarding the state of an object (such as In or At)                    Also known as propositions or facts                        A set of propositions called the Initial Conditions                    Package A on Earth, Package B on Earth, Rocket on Earth                        A set of Problem Goals which are propositions that are required to be true at the end of a plan                    Package A on the Moon, Package B on the Moon                        
In STRIPS, each effect will either “Add” or “Delete” a proposition from the knowledge base. The effect of “Add” is to make the proposition true. The effect of “Delete” is to make the proposition false.
A planning graph consists of a set of levels. The first level is a set of propositions that correspond to the initial conditions. The second level is a set of actions (applied operators) that can be performed given the previous level of propositions. The subsequent level is a set of propositions that would be true if the previous level actions were to be applied.
The Graphplan algorithm begins by taking the known propositions in level 0 and attempts to apply all possible actions with preconditions that match those available. For every proposition, a No-Operation action is also applied. This results in a set of propositions at the next level, called level 1. The subsequent levels repeat this process until a set of propositions are found that match the goal state, or until no new actions may be applied in a given level. At each level, the number of applicable actions or propositions is restricted by the concept of mutual exclusion (mutex).
Thus, two facts f1, f2 ε Nf (n ≧1) are mutually exclusive if no valid plan could possibly make both true. There is no non-exclusive pair of actions o1, o2 ε No(n−1)• and no single action o ε No(n−1) that adds f1 and f2.
A mutex action pair occurs under three conditions: Inconsistent Effects, Interference and Competing Needs:                Inconsistent Effects occur when the effect of one action is the negation of another action's effects;        Interference occurs if either action deletes a precondition the other; and        Competing Needs occurs if any preconditions for a pair of actions are marked as mutex. A pair of propositions is marked as mutex if all ways of creating one proposition are exclusive of creating the other, or of one is the negation of the other.        
In this context, two actions o1 and o2 have “Inconsistent Effects” if the effect of one action is the negation of another. Two actions o1 and o2 “Interfere” if either of the actions deletes a precondition of the other. Two actions o1 and o2 at an action level No (n ≧1) have Competing Needs if there is a precondition of action o1 and a precondition of action b that are marked as mutually exclusive.
An example of mutex actions in the rocket domain includes “Load A” and “Fly to the Moon”. Clearly, one cannot fly to the moon at the same time that one is loading the rocket. “Fly to the Moon” deletes the precondition of “Load A”, which is that A must be in the same location as the rocket. The propositions that “Rocket on the Moon” and “Rocket on the Earth” are clearly mutually exclusive and cannot exist at the same time frame in a plan.
Once a planning graph is constructed, a backward chaining algorithm is used to determine the best possible path backwards through the graph. In the landmark paper titled “Fast Planning Through Planning Graph
Analysis”, Blum and Furst were able to prove that Graphplan will find a plan if one exists in polynomial time, or will detect that no solution exists within polynomial time. This was a very important result in the planning community because it validated the applicability of planning for a variety of real-world situations.
The operation of the Graphplan Algorithm is now summarized:
Graphplan Algorithm  Add initial conditions  Find out which ones are mutex  Repeat until done:    Check to see which actions can apply (no mutex preconditions)      If no actions can be applied then a plan cannot be found      Add all actions that apply (no mutex preconditions) given      current conditions      Find out which actions are mutex    Discover new conditions given application of all possible actions    Find out which conditions are mutex    If current conditions meet goal conditions then      Check to see if a plan can be found by backchaining to      initial conditions      Mutex actions cannot occur in the same time frame of a      plan      If a plan can be found then graphplan is done  End repeatEnd Graphplan
Overall, automatic workflow generation is closely related to AI planning: it can be treated as a special planning problem and solved by appropriate planner systems. Work has been done on automatic web service synthesis based on AI planning. Though most approaches map web service synthesis into AI planning, the web service domain has its own special characteristics and current AI planning is unlikely to provide a complete solution. First, a web service (task) often has multiple outcomes and nondeterministic behavior. Second, work-low languages provide a set of control constructs, and the synthesis algorithm needs to choose the constructs wisely in order to produce a well structured workflow. Classic planning focuses on generating a path for conjunctive goals and does not consider actions with conditional or nondeterministic effects. Recently, planning algorithms have been developed to handle more complex situations, such as conditions and nondeterminism. However, they are not intended to generate structured workflows.